package ink.lvxin.datastructure.ch2;

import ink.lvxin.datastructure.utils.NumberUtils;
import ink.lvxin.datastructure.utils.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 一些O(logN)的算法
 * @author lx
 */
public class SomeLogN {
    private static Logger logger = LoggerFactory.getLogger(SomeLogN.class);

    /**
     * 折半查找
     * @param sortedArr
     * @param toFind
     * @param left
     * @param right
     * @return
     * @throws Exception
     */
    public static int binarySearch(int[] sortedArr,int toFind,int left,int right) throws Exception {
        int value;
        if (left == right) {
            value = sortedArr[left];
            if (value == toFind) {
                return left;
            }

            throw new Exception("the number is not in arr..");
        }


        int mid = (left + right) / 2;
        if (toFind == sortedArr[mid]) {
            return mid;
        }

        if (toFind > sortedArr[mid]) {
            return binarySearch(sortedArr, toFind, mid + 1, right);
        }else {
            return binarySearch(sortedArr, toFind, left, mid);
        }

    }

    /**
     * 欧几里得算法，求最大公因数
     * @param m
     * @param n
     * @return
     */
    public static long gcd(long m, long n) {
        while (n > 0) {
            long rem = m % n;
            m = n;
            n = rem;
        }

        return m;
    }

    public static void main(String[] args) throws Exception {
        testBinarySearch();
//        testGcd();
    }

    private static void testGcd() {
        System.out.println(gcd(344319892,333431590));
    }

    private static void testBinarySearch() {
        int[] arr = NumberUtils.getBigSortedArr(1000000,1);
        System.out.println(StringUtils.join(arr,","));

        long start = System.currentTimeMillis();
        try {
            System.out.println(binarySearch(arr, 888, 0, arr.length));
        } catch (Exception e) {
            logger.error(e.getMessage(),e);
        }
        System.out.println("binarySearch costs:" + (System.currentTimeMillis() - start) + " ms");
    }
}
